package
{
	public class SkipList
	{
		public var rootNode:SkipListNode;
		
		public function SkipList()
		{
			rootNode = new SkipListNode();
			rootNode.listNodes[0] = new ListNode(rootNode);
		}
		public var heightCount:Object = new Object();
		
		public function insert(num:Number):void{
			// @todo - better way of getting a random number with an exponential distribution
			
			var random:int = Global.prng.nextIntRange(0, Math.pow(2,rootNode.listNodes.length)-1);
			var selectedTier:SkipListTier;
			var count:int = 0;
			var increaseHeight:Boolean = false;
			if(random == 0){
				increaseHeight = true;
			}			
			
			for(var i:int = 0; i < rootNode.listNodes.length; i++){
				random -= Math.pow(2,i);
				count++;
				if(random < 0){
					break;
				}
				
			}

			if(increaseHeight){
				rootNode.listNodes[rootNode.listNodes.length] = new ListNode(rootNode);
			}			
			
			var height:int = rootNode.listNodes.length - count;
			if(heightCount[height] == null){
				heightCount[height] = 0;
			}
			heightCount[height]++;
			
			var nodeToInsert:SkipListNode = new SkipListNode(new SkipListValue(num));
			var next:SkipListNode;
			var insertionPoint:SkipListNode = getInsertionNode(num);
			for(i = 0; i < height + 1; i++){
				nodeToInsert.listNodes[i] = new ListNode(nodeToInsert);
				nodeToInsert.listNodes[i].nextNode = insertionPoint.listNodes[i].nextNode;
				insertionPoint.listNodes[i].nextNode = nodeToInsert.listNodes[i];
			}
			
		}
		
		public function getSortedList():Array{
			var nextListNode:ListNode = rootNode.listNodes[0].nextNode;
			var values:Array = new Array();
			while(nextListNode != null){
				values.push(nextListNode.parent.data.value);
				nextListNode = nextListNode.nextNode;
			}
			
			return values;
		}
		
		private function getInsertionNode(val:Number):SkipListNode{
			var insertionNode:SkipListNode = rootNode.clone();
			find(val, this.rootNode.getTopNode(), insertionNode);
			return insertionNode;
		}
		
		private function find(val:Number, curListNode:ListNode, insertionNode:SkipListNode, depth:int = 1):Boolean{
			var currentTier:int = rootNode.listNodes.length - depth;
			var found:Boolean = false;
			var nextListNode:ListNode = curListNode.nextNode;
			insertionNode.listNodes[currentTier] = curListNode;
			
			
			if(nextListNode == null){
				if(currentTier > 0){
					found = find(val, curListNode.parent.listNodes[currentTier - 1], insertionNode, ++depth);
				}
			} 
			else {
				if(nextListNode.parent.data.value == val){
					for(var i:int = 0; i < currentTier; i++){
						insertionNode.listNodes[i] = nextListNode.parent.listNodes[i];
					}
					found = true;
				}
				else if(nextListNode.parent.data.value < val){
					found = find(val, nextListNode, insertionNode, depth);
				}
				else {
					if(currentTier > 0){
						found = find(val, curListNode.parent.listNodes[currentTier - 1], insertionNode, ++depth);
					}
				}
			}

			return found;
		}
	}
}